package zhai.tree;

// https://www.bilibili.com/video/BV1nK411L7H9?p=32
// 二叉搜索树
// 时间复杂度　logn
// 20亿个点查询　32次　2^32=21亿
// 注意：一定要排序取中位数，如果取了最小或最大数，会导致退化成链表
public class BinarySearchTree {

    private int data;
    private BinarySearchTree right;
    private BinarySearchTree left;

    public BinarySearchTree(int data) {
        this.data = data;
        this.right = null;
        this.left = null;
    }

    public void insert(BinarySearchTree root, int data) {
        //　根节点　小于data 插入右子树
        if (root.data < data) {
            // 右边没有值直接插入
            if (root.right == null) {
                root.right = new BinarySearchTree(data);
            } else {
                insert(root.right, data);
            }
        } else {
             if (root.left == null) {
                root.left = new BinarySearchTree(data);
            } else {
                insert(root.left, data);
            }
        }
    }

    // 中序遍历 :左根(输出)右
    public void in(BinarySearchTree root) {
        if (root != null) {
            in(root.left);
            System.out.println(root.data + " ");
            in(root.right);
        }
    }

    public static void main(String[] args) {
        int data[] = {5,9,0,1,2,3,10};
        BinarySearchTree root = new BinarySearchTree(data[0]); // 序列第一个作为root节点
        for (int i = 1; i < data.length; i++) {
            root.insert(root, data[i]);
        }
        System.out.println("中序遍历为：");
        root.in(root);

    }
}
